package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:莫里斯遍历
 * 莫里斯遍历是一种使用O(1)额外空间的二叉树遍历方法，它能够实现中序遍历（也可以稍作修改实现前序遍历和后序遍历）。
 *
 * 这种遍历方法的核心思想是，通过修改树的结构，将原始树的右子树连接到某个节点的前驱上，以便在遍历完该节点的左子树后，能够在O(1)时间内访问到该
 * 节点的右子树。具体步骤如下：
 *
 * 1.初始化当前节点为根节点。
 *
 * 2.如果当前节点的左子树为空，输出当前节点的值并将当前节点更新为其右子节点。
 *
 * 3.如果当前节点的左子树不为空，找到当前节点的左子树的最右边的节点，即当前节点的左子树的中序遍历的最后一个节点（这个节点被称为当前节点的前驱节点）。
 *
 * 4.将当前节点连接到其前驱节点的右子节点（如果前驱节点的右子节点为空，将其指向当前节点，如果前驱节点的右子节点不为空，将其指向null），然后将当前
 * 节点更新为其左子节点。
 *
 * 5.重复步骤2和步骤3，直到当前节点为空。
 * author: Mr.Du
 * Date: 2023/9/3
 * Time: 10:20
 */
public class MorrisTraversal {

    public static void morrisInorderTraversal(TreeNode root) {
        TreeNode current = root;

        while (current != null) {
            if (current.left == null) {
                System.out.print(current.val + " ");
                current = current.right;
            } else {
                // 一直找到当前左孩子的最右孩子
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // 将遍历的当前节点的右孩子指向当前current节点
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // 移除线索连接并访问当前节点
                    predecessor.right = null;
                    System.out.print(current.val + " ");
                    current = current.right;
                }
            }
        }
    }

    public static void morrisPreorderTraversal(TreeNode root) {
        TreeNode current = root;

        while (current != null) {
            if (current.left == null) {
                System.out.print(current.val + " ");
                current = current.right;
            } else {
                // Find the in-order predecessor (the rightmost node in the left subtree)
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    // Make the threaded connection
                    System.out.print(current.val + " ");  // Visit before going left
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Remove the threaded connection
                    predecessor.right = null;
                    current = current.right;
                }
            }
        }
    }

    public static void morrisPostorderTraversal(TreeNode root) {
        TreeNode dummy = new TreeNode(0);  // 创建一个虚拟节点作为辅助节点
        dummy.left = root;
        TreeNode current = dummy;

        while (current != null) {
            if (current.left == null) {
                current = current.right;
            } else {
                // Find the in-order predecessor (the rightmost node in the left subtree)
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // Make the threaded connection
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Remove the threaded connection and visit nodes along the way
                    reverseVisit(current.left, predecessor);
                    predecessor.right = null;
                    current = current.right;
                }
            }
        }
    }

    public static void reverseVisit(TreeNode from, TreeNode to) {
        reverse(from, to);
        TreeNode current = to;
        while (true) {
            System.out.print(current.val + " ");
            if (current == from) {
                break;
            }
            current = current.right;
        }
        reverse(to, from);
    }

    public static void reverse(TreeNode from, TreeNode to) {
        if (from == to) {
            return;
        }
        TreeNode x = from;
        TreeNode y = from.right;
        TreeNode z;
        while (x != to) {
            z = y.right;
            y.right = x;
            x = y;
            y = z;
        }
    }




    public static void main(String[] args) {
        // Create a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.print("In-order traversal: ");
        morrisInorderTraversal(root);
        System.out.println();
        System.out.print("Pre-order traversal: ");
        morrisPreorderTraversal(root);
        System.out.println();
        System.out.print("Post-order traversal: ");
        morrisPostorderTraversal(root);

    }
}
